Corelab Seminar
2010-2011
Haris Angelidakis (NTUA)
Approximation algorithms for Stochastic Combinatorial Optimization Problems
Abstract.
In this talk, we will conclude our overview of the research done in the field of Stochastic Combinatorial Optimization the last decade. Stochastic Optimization attempts to model uncertainty in the input data. More specifically, it studies decision making when only probabilistic information about the input is given, and not the actual input data. The concept of having to make decisions under uncertainty about future requirements rises naturally in many areas, including transportation models, logistics, financial instruments and network design. In such cases, while more effective decisions can be made when the actual requirements are given, the decision-making costs are inflated until then.
We will revisit some fundamental concepts of the field, and then proceed to present approximation algorithms for both 2-stage and multistage problems. Various notions and techniques will be presented, such as cost-sharing functions, sampling techniques and linear and convex optimization techniques (with a special focus on the ellipsoid algorithm) which combined with rounding techniques can give approximation algorithms for several combinatorial optimization problems, such as covering problems (Set Cover, Vertex Cover) and Facility Location Problems.
We will finish our talk by stating some open problems in the field and introducing the risk-aversion variant of the problems studied. We will also make a connection between stochastic optimization problems and leasing problems, where we lease rather than buy elements in order to satisfy demands that change over a period of time.